package xyz.xiaotugou.dataStructure.stack;


public class MyStackBaseOnArray {
	 private int[] array;
     private int size = 0;
     private int length = 1024;

     public static int binarySearch(int[] array,int key){
 		int start=0;
 		int mid;
 		int end=array.length-1;
 		while(start<=end){
 			mid=(end-start)/2+start;
 			if(key<array[mid]){
 				end=mid-1;
 			}
 			else if(key>array[mid]){
 				start=mid+1;
 			}else{
 				return mid;
 			}
 		}
 		return -1;
 	}
     
    /*使用斐波那契数列，解决青蛙台阶问题：时间复杂度O(n)、空间复杂度O(1)*/
	public int climbStairs(int n) {
	    if ( n == 1) {
	       return 1;
	    }
	    int first = 1;
	    int second = 2;
	    for (int i = 3; i <= n; i++) {
	        int third = first + second;
	        first = second;
	        second = third;
	    }
	    return second;
	}
     /*
      * 构造方法，初始化基本结构
      */
     public MyStackBaseOnArray() {
         array = new int[length];
     }

     /*
      * 入栈操作
      */
     public void push(int x) {
         if(size==length){
             int lastLength = length;
             length = length+lastLength;
             int [] listTemp = new int[length];
             for(int i = 0;i < lastLength;i++){
                 listTemp[i] = array[i];
             }
             array = listTemp;
         }
         array[size++] = x;
     }

     /** Removes the element on top of the stack and returns that element. */
     public int pop() {
         return array[--size];
     }

     /** Get the top element. */
     public int top() {
         return array[size-1];
     }

     /** Returns whether the stack is empty. */
     public boolean empty() {
         if(size==0){
             return true;
         }
         return false;
     }
}
